<head>
    <meta charset="UTF-8">
<title>算法训练 Maxim and Calculator</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【试题来源】</p>
<p>&nbsp;</p>
<p>Codeforces 261E</p>
<p>【问题描述】<br />
<span style="color: rgb(34, 34, 34); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.63636302948px; line-height: 19.6000003814697px;">Maxim 得到了一个计算器，这个计算器有两个整数单元，一开始，第一个单元包含数字1，第二个单元包含数字0。 这个计算器支持一以下两种操作：</span></p>
<p>&nbsp;</p>
<p>1.假设第一个单元的数字为a，第二个单元的数字为b，那么将第二个单元的数字改成b+1。</p>
<p>&nbsp;</p>
<p>2.假设第一个单元的数字为a，第二个单元的数字为b，那么将第一个单元的数字改成a*b。</p>
<p>&nbsp;</p>
<p>现在<span style="color: rgb(34, 34, 34); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 19.6000003814697px;">Maxim&nbsp;想知道，有多少个正整数x(l&lt;=x&lt;=r)满足， 存在一种方式从计算器初始状态开始，操作不超过p步之后使得第一个单元中的数字为x。</span><br />
【输入格式】<br />
共一行，为三个空格隔开的正整数(2&lt;=l&lt;=r&lt;=10^9, 1&lt;=p&lt;=100)<br />
【输出格式】<br />
输出仅一行一个整数ans，即为问题所求。<br />
【样例输入I】</p>
<p>&nbsp;</p>
<p>2 10 3</p>
<p>【样例输出I】</p>
<p>&nbsp;</p>
<p>1</p>
<p>&nbsp;</p>
<p>【样例输入II】</p>
<p>&nbsp;</p>
<p>2 111 100</p>
<p>&nbsp;</p>
<p>【样例输出II】</p>
<p>&nbsp;</p>
<p>106</p>
<p>&nbsp;</p>
<p>【样例输入III】</p>
<p>&nbsp;</p>
<p>2 111 11</p>
<p>&nbsp;</p>
<p>【样例输出III】</p>
<p>&nbsp;</p>
<p>47<br />
【数据规模和约定】<br />
30%的数据满足，2&lt;=l&lt;=r&lt;=10^6,1&lt;=p&lt;=15。</p>
<p>&nbsp;</p>
<p>另外20%的数据满足，2&lt;=l=r&lt;=10^9,1&lt;=p&lt;=100。</p>
<p>&nbsp;</p>
<p>100%的数据满足，2&lt;=l&lt;=r&lt;=10^9,1&lt;=p&lt;=100.</p>